package com.azure.code.graph.bipartite;

import java.util.LinkedList;
import java.util.List;

/**
 * 886 可能的二分法
 * 给定一组n人（编号为1, 2, ..., n），我们想把每个人分进任意大小的两组。
 * 每个人都可能不喜欢其他人，那么他们不应该属于同一组。
 * <p>
 * 给定整数 n和数组 dislikes，其中dislikes[i] = [ai, bi]，
 * 表示不允许将编号为 ai和bi的人归入同一组。当可以用这种方法将所有人分进两组时，
 * 返回 true；否则返回 false。
 * <p>
 * <p/>示例：
 * 输入：n = 4, dislikes = [[1,2],[1,3],[2,4]]
 * 输出：true
 * 解释：group1 [1,4], group2 [2,3]
 */
public class BipartiteGraph_886 {
    boolean[] visited;
    boolean[] color;
    boolean ok = true;

    /**
     * 转化成 二分图  双色问题
     */
    public boolean possibleBipartition(int n, int[][] dislikes) {
        // 图节点从1开始
        visited = new boolean[n + 1];
        color = new boolean[n + 1];
        // 转化成邻接表表示图结构
        List<Integer>[] graph = buildGraph(n, dislikes);

        for (int v  = 1; v <= n; v++) {
            if(!visited[v]){
                dfs(graph,v);
            }
        }
        return !ok;
    }

    private void dfs(List<Integer>[] graph, int v) {
        if(!ok) return;
        visited[v] = true;
        for (Integer w : graph[v]) {
            if(!visited[w]){
                color[w]=!color[v];
                dfs(graph,w);
            }else {
                if(color[w]!=color[v]){
                    ok = false;
                    return;
                }
            }
        }
    }

    // 建图函数
    private List<Integer>[] buildGraph(int n, int[][] dislikes) {
        List<Integer>[] graph = new LinkedList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new LinkedList<>();
        }
        for (int[] edge : dislikes) {
            int v = edge[1];
            int w = edge[0];
            // 无向图 相当于双向图
            graph[v].add(w);
            graph[w].add(v);
        }
        return graph;
    }
}
